package day40;

// 最长上升子序列（长度）
// 动归问题dp


import java.util.Scanner;

public class Main2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] nums = new int[n];
            // 进行数据的初始化
            for (int i = 0; i < n; i++) {
                nums[i] = in.nextInt();
            }
            int[] dp = new int[n];
            dp[0] = 1;
            int ret = 1; // 存放最长的子序列长度
            // 遍历寻找最长上升子序列（两次遍历！）
            // 关键点！！
            for (int i = 0; i < n; i++) { // 标志最终每次遍历的结束位置，也就是每次都寻找此前的上升序列
                dp[i] = 1; // 该位置最少长度都有1
                for (int j = 0; j <= i; j++) { // 每次寻找都是从起始位置开始的
                    if (nums[j]<nums[i] && dp[j]>=dp[i]) {
                        dp[i] = dp[j] + 1;
                        ret = dp[i]>ret? dp[i]:ret;
                    }
                }
            }
            System.out.println(ret);
        }
    }
}
